package com.hardy.leecode;

import com.hardy.leecode.model.Node;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Author: Hardy
 * Date:   2020/9/28
 * Description:
 * 给定一个二叉树
 * <p>
 * 117. 填充每个节点的下一个右侧节点指针 II
 * <p>
 * struct Node {
 * int val;
 * Node *left;
 * Node *right;
 * Node *next;
 * }
 * 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
 * <p>
 * 初始状态下，所有 next 指针都被设置为 NULL。
 * <p>
 * 进阶：
 * <p>
 * 你只能使用常量级额外空间。
 * 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
 *  
 * 输入：root = [1,2,3,4,5,null,7]
 * 输出：[1,#,2,3,#,4,5,7,#]
 * 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。
 *  
 * <p>
 * 提示：
 * <p>
 * 树中的节点数小于 6000
 * -100 <= node.val <= 100
 **/
public class Que117 {

    public static void main(String[] args) {

        System.out.println(new Temp.Solution());
    }

    static class Solution {

        public Node connect(Node root) {
            if (root == null) return null;

            Node node = root;
            Node nextHead = null;
            Node nextNode = null;

            while (node != null) {
                if (node.left != null) {
                    if (nextHead == null) {
                        nextHead = node.left;
                        nextNode = node.left;
                    } else {
                        nextNode.next = node.left;
                        nextNode = nextNode.next;
                    }
                }

                if (node.right != null) {
                    if (nextHead == null) {
                        nextHead = node.right;
                        nextNode = node.right;
                    } else {
                        nextNode.next = node.right;
                        nextNode = nextNode.next;
                    }
                }

                if (node.next != null) {
                    node = node.next;
                } else {
                    node = nextHead;
                    nextHead = null;
                    nextNode = null;
                }
            }
            return root;
        }

        public Node connect1(Node root) {
            if (root == null) return null;

            Queue<Node> q = new LinkedList<>();
            q.offer(root);

            while (!q.isEmpty()) {
                int size = q.size();
                Node front = null;

                for (int i = 0; i < size; i++) {
                    Node node = q.poll();

                    if (front != null) front.next = node;
                    front = node;

                    if (node.left != null) q.offer(node.left);
                    if (node.right != null) q.offer(node.right);
                }
            }
            return root;
        }
    }
}
